package top.ivansong92.example.leetcode.learning.data.struct.linklist;


import org.junit.Test;

import java.util.*;

public class TestExampleV2 {
    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {}
        ListNode(int x) {
            val = x;
        }

        public static ListNode attrToListNode(int[] attr) {
           if (attr == null || attr.length == 0) {
               return null;
           }
           ListNode head = new ListNode(attr[0]);
           ListNode cur = head;
           for(int i = 1; i < attr.length; i ++) {
               cur.next = new ListNode(attr[i]);
               cur = cur.next;
           }
           return head;
        }

        @Override
        public String toString() {
            StringBuffer stringBu = new StringBuffer();
            stringBu.append("[");
            ListNode cur = this;
            while (cur != null) {
                stringBu.append(cur.val + "->");
                cur = cur.next;
            }
            stringBu.append("null]");
            return stringBu.toString();
        }
    }

    /**
     * 92. 反转链表 II
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }

        List<ListNode> nodeList = new ArrayList<>();
        ListNode idx = head;
        while (idx != null) {
            nodeList.add(idx);
            idx = idx.next;
        }

        ListNode res = new ListNode();
        idx = res;
        for (int i = 0; i < nodeList.size() && i < left - 1; i++) {
            ListNode node = new ListNode(nodeList.get(i).val);
            idx.next = node;
            idx = idx.next;
        }

        int end = right >= nodeList.size() ? nodeList.size() - 1 : right - 1;
        for (int i = end; i >= left - 1; i--) {
            ListNode node = new ListNode(nodeList.get(i).val);
            idx.next = node;
            idx = idx.next;
        }

        for (int i = end + 1; i < nodeList.size(); i++) {
            ListNode node = new ListNode(nodeList.get(i).val);
            idx.next = node;
            idx = idx.next;
        }

        return res.next;
    }


    public ListNode reverseBetweenV2(ListNode head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode res = new ListNode();
        res.next = head;
        ListNode idx = res;
        for (int i = 1; i < left && idx != null; i++) {
            idx = idx.next;
        }

        if (idx == null) {
            return res.next;
        }
        ListNode cur = idx.next, next;
        for(int i = left; i < right && cur.next != null; i ++) {
            next = cur.next;
            cur.next = next.next;
            next.next = idx.next;
            idx.next = next;
        }


        return res.next;
    }


    /**
     * 86. 分隔链表
     * @param head
     * @param x
     * @return
     */

    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return new ListNode(x);
        }

        ListNode less = new ListNode(0);
        ListNode more = new ListNode(0);
        ListNode idx = head, lessIdx = less, moreIdx = more;
        while (idx != null) {
            if (idx.val < x) {
                lessIdx.next = new ListNode(idx.val);
                lessIdx = lessIdx.next;
            } else {
                moreIdx.next = new ListNode(idx.val);
                moreIdx = moreIdx.next;
            }
            idx = idx.next;
        }
        lessIdx.next = more.next;
        return less.next;
    }


    /**
     * 328. 奇偶链表
     * @param head
     * @return
     */

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode left = res.next, plus = left.next, right = plus;
        while (right != null && right.next != null) {
            left.next = right.next;
            right.next = right.next.next;
            right = right.next;
            left = left.next;
        }
        left.next = plus;

        return res.next;
    }


    /**
     * 2. 两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        ListNode res = new ListNode(0);
        ListNode idx = res, idxL1 = l1, idxL2 = l2;
        int plus = 0, total;
        while (idxL1 != null || idxL2 != null) {
            total = plus + (idxL1 != null ? idxL1.val : 0) +   (idxL2 != null ? idxL2.val : 0);
            idx.next = new ListNode(total % 10);
            plus = total / 10;
            if (idxL1 != null) {
                idxL1 = idxL1.next;
            }

            if (idxL2 != null) {
                idxL2 = idxL2.next;
            }

            idx = idx.next;

        }
        if (plus > 0) {
            idx.next = new ListNode(plus);
        }
        return res.next;

    }

    /**
     * 2. 两数相加
     * @param l1
     * @param l2
     * @return
     */
    public ListNode add2Numbers(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        ListNode re1 = reverseList(l1);
        ListNode re2 = reverseList(l2);

        ListNode res = new ListNode(0);
        ListNode idx = res, idxL1 = re1, idxL2 = re2;
        int plus = 0, total;
        while (idxL1 != null || idxL2 != null) {
            total = plus + (idxL1 != null ? idxL1.val : 0) +   (idxL2 != null ? idxL2.val : 0);
            idx.next = new ListNode(total % 10);
            plus = total / 10;
            if (idxL1 != null) {
                idxL1 = idxL1.next;
            }

            if (idxL2 != null) {
                idxL2 = idxL2.next;
            }

            idx = idx.next;

        }

        if (plus > 0) {
            idx.next = new ListNode(plus);
        }

        return reverseList(res.next);
    }

    private ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res = new ListNode(head.val);

        ListNode cur = head.next;
        while(cur != null) {
            ListNode node = new ListNode(cur.val);
            node.next = res;
            res = node;
            cur = cur.next;
        }
        return res;
    }

    @Test
    public void testSwapPairs() {
        System.out.println(swapPairs(ListNode.attrToListNode(new int[]{1,2,3,4})));
    }
    /**
     * 24. 两两交换链表中的节点
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }


        ListNode cur = head, next = cur.next, c1, c2, res = null;
        while (cur != null && next != null) {
            c1 = cur;
            c2 = next;
            cur = next.next;
            if (cur != null) {
                next = cur.next;
            } else {
                next = null;
            }

            c1.next = next == null && cur != null ? cur : next;
            c2.next = c1;
            if (res == null) {
                res = c2;
            }
        }
        return res;
    }


    public ListNode swapPairsV2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode res = new ListNode();
        res.next = head;
        ListNode resCur = res, node1 = head, node2 = head.next, tmpNext;
        while (node1 != null && node2 != null) {
            tmpNext = node2.next;
            node1.next = tmpNext;
            node2.next = node1;
            resCur.next = node2;
            resCur = node1;
            node1 = tmpNext;
            if (node1 != null) {
                node2 = node1.next;
            } else {
                node2 = null;
            }
        }
        return res.next;
    }


    /**
     * 25. K 个一组翻转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        List<Integer> nodeList = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            nodeList.add(cur.val);
            cur = cur.next;
        }

        int len = nodeList.size();

        if (len < k) {
            return head;
        }

        ListNode res = new ListNode(0);
        cur = res;

        for (int i = 0; i < len; i += k) {
            for (int j = i + k - 1; j >= i && j < len; j--) {
                cur.next = new ListNode(nodeList.get(j));
                cur = cur.next;
            }
        }

        int plus = len % k;
        if (plus != 0) {
            for (int i = len - plus; i < len; i++) {
                cur.next = new ListNode(nodeList.get(i));
                cur = cur.next;
            }
        }

        return res.next;
    }


    @Test
    public void testReverseKGroupV2() {
        System.out.println(reverseKGroupV2(ListNode.attrToListNode(new int[]{1,2,3,4, 5}), 2));
    }

    public ListNode reverseKGroupV2(ListNode head, int k) {
        if (head == null || head.next == null || k == 1) {
            return head;
        }
        ListNode res = new ListNode(0);
        ListNode resCur = res, cur = head;
        ListNode[] tmpArray = new ListNode[k];
        int counter = 1;
        while (cur != null) {
            tmpArray[counter - 1] = cur;
            cur = cur.next;
            tmpArray[counter - 1].next = null;
            if (counter % k == 0) {
                for (int i = k - 1; i >= 0; i--) {
                    resCur.next = tmpArray[i];
                    resCur = resCur.next;
                }
                tmpArray = new ListNode[k];
                counter = 1;
                continue;
            }
            counter++;
        }

        for (ListNode node : tmpArray) {
            if (node != null) {
                resCur.next = node;
                resCur = resCur.next;
            }
        }
        return res.next;
    }

    /**
     * 147. 对链表进行插入排序
     * @param head
     * @return
     */
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0), idx = dummy.next;
        ListNode cur = head;
        while (cur != null) {
            if (idx == null) {
                dummy.next = new ListNode(cur.val);
                idx = dummy.next;
                cur = cur.next;
                continue;
            }

            int val = cur.val;
            if (val >= idx.val) {
                idx.next = new ListNode(val);
                idx = idx.next;
            } else {
                ListNode tmp = dummy.next, pre = dummy;
                while (tmp != null) {
                    if (tmp.val < val) {
                        pre = tmp;
                        tmp = tmp.next;
                    } else {
                        pre.next = new ListNode(val);
                        pre.next.next = tmp;
                        break;
                    }
                }
            }
            cur = cur.next;
        }
        return  dummy.next;
    }




    @Test
    public void testRotateRight() {
        System.out.println(rotateRight(ListNode.attrToListNode(new int[]{1,2,3,4, 5}), 2));
    }

    /**
     * 61. 旋转链表
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if (k <= 0 || head == null || head.next == null) {
            return head;
        }

        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }

        int plus = k % len;
        if (plus == 0) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur1 = dummy;
        cur = dummy;
        for (int i = 0; i < plus; i++) {
            cur = cur.next;
        }

        while (cur.next != null) {
            cur = cur.next;
            cur1 = cur1.next;
        }

        cur = cur1;
        ListNode next = cur1.next;
        while (cur1.next != null) {
            cur1 = cur1.next;
        }

        cur1.next = dummy.next;
        dummy.next = next;
        cur.next = null;
        return dummy.next;
    }

    /**
     * 143. 重排链表
     * @param head
     */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }

        //计算长度
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }

        //找到中点
        cur = head;
        int step = (len / 2 + len % 2) - 1;
        for (int i = 0; i < step; i++) {
            cur = cur.next;
        }

        //分割成两个链表
        ListNode cur1 = head, cur2 = cur.next, next1, next2;
        cur.next = null;
        //后面链表做一下反转
        cur2 = reversNodeList(cur2);
        //合并两个链表
        while (cur1 != null) {
            next1 = cur1.next;
            cur1.next = cur2;
            if (cur2 != null) {
                next2 = cur2.next;
                cur2.next = next1;
            } else {
                next2 = null;
            }
            cur1 = next1;
            cur2 = next2;
        }
    }

    private ListNode reversNodeList(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }

        ListNode cur = node, next, pre = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }


    @Test
    public void testsortList() {
        System.out.println(sortListV2(ListNode.attrToListNode(new int[]{4,2,1,3})));
    }

    /**
     * 148. 排序链表
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode leftDum = new ListNode();
        ListNode rightDum = new ListNode();
        ListNode right = rightDum, left = leftDum;
        int val = head.val;
        ListNode next = head.next;
        head.next = null;
        while (next != null) {
            if (next.val > val) {
                right.next = next;
                next = next.next;
                right = right.next;
                right.next = null;
            } else {
                left.next = next;
                next = next.next;
                left = left.next;
                left.next = null;
            }
        }

        leftDum.next = sortList(leftDum.next);
        left = leftDum;
        ListNode leftNext = left.next;
        while (leftNext != null) {
            left = leftNext;
            leftNext = leftNext.next;
        }

        left.next = head;

        head.next = sortList(rightDum.next);

        return leftDum.next;
    }


    public ListNode sortListV2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        return doMergeSortList(head);
    }
    private ListNode doMergeSortList(ListNode node) {
        if (node == null || node.next == null) {
            return node;
        }

        ListNode slow = node, fast = node, pre = null;
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }
        }
        pre.next = null;
        ListNode node1 = doMergeSortList(node);
        ListNode node2 = doMergeSortList(slow);
        return merge(node1, node2);
    }
    private ListNode merge(ListNode n1, ListNode n2) {
        ListNode dum = new ListNode();
        ListNode idx = dum;
        while (n1 != null && n2 != null) {
            if (n1.val > n2.val) {
                idx.next = n2;
                idx = idx.next;
                n2 = n2.next;
            } else {
                idx.next = n1;
                idx = idx.next;
                n1 = n1.next;
            }
        }
        if (n1 != null) {
            idx.next = n1;
        }
        if (n2 != null) {
            idx.next = n2;
        }
        return dum.next;
    }


    @Test
    public void testfindKthLargest() {
        System.out.println(findKthLargest(new int[]{3,2,1,5,6,4}, 2));
    }

    /**
     * 215. 数组中的第K个最大元素
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return -1;
        }

        return doFindKth(nums, k, 0, nums.length - 1);
    }

    private int doFindKth(int[] nums, int k, int from, int to) {
        int val = nums[k - 1];
        nums[k - 1] = nums[from];
        nums[from] = val;
        int i = from, j = to;
        while (i < j) {
            while (i < j && nums[j] <= val) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] >= val) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = val;
        if (i == k - 1) {
            return nums[i];
        } else if (i > k - 1) {
            return doFindKth(nums, k, from, i - 1);
        } else {
            return doFindKth(nums, k, i + 1, to);
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        int len = nums.length;
        if (len == 1) {
            return Collections.singletonList(Collections.singletonList(nums[0]));
        }
        List<List<Integer>> res = new ArrayList<>();
        boolean[] flag = new boolean[len];
        dsf(nums, flag, new ArrayList<>(), res);
        return res;
    }

    private void dsf(int[] nums, boolean[] flag, List<Integer> parent, List<List<Integer>> res) {
        if (parent.size() == nums.length) {
            res.add(new ArrayList<>(parent));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (flag[i]) {
                continue;
            }
            flag[i] = true;
            parent.add(nums[i]);
            dsf(nums, flag, parent, res);
            flag[i] = false;
            parent.remove(parent.size() - 1);
        }
    }


    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Collections.emptyList();
        }

        int len = nums.length;
        if (len == 1) {
            return Collections.singletonList(Collections.singletonList(nums[0]));
        }
        Arrays.sort(nums);

        List<List<Integer>> res = new ArrayList<>();
        boolean[] flag = new boolean[len];
        dsfV2(nums, flag, new ArrayList<>(), res);
        return res;
    }

    private void dsfV2(int[] nums, boolean[] flag, List<Integer> parent, List<List<Integer>> res) {
        if (parent.size() == nums.length) {
            res.add(new ArrayList<>(parent));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (flag[i] || (i > 0 && nums[i] == nums[i - 1] && flag[i-1])) {
                continue;
            }

            flag[i] = true;
            parent.add(nums[i]);
            dsfV2(nums, flag, parent, res);
            flag[i] = false;
            parent.remove(parent.size() - 1);
        }
    }


    public List<List<Integer>> combinationSum3(int k, int n) {
        if (k > 9 || k < 1 || n < 1 || n > 45) {
            return Collections.emptyList();
        }

        List<List<Integer>> res = new ArrayList<>();
        doCombinationSum3(1, 9, n, k, new ArrayList<>(), res);
        return res;
    }

    private void doCombinationSum3(int from, int to, int target, int len, List<Integer> array, List<List<Integer>> res) {
        if (array.size() == len) {
            if (target == 0) {
                res.add(new ArrayList<>(array));
            }
            return;
        }
        for (int i = from; i <= to; i++) {
            if (i > target) {
                break;
            }
            array.add(i);
            doCombinationSum3(i + 1, to, target - i, len, array, res);
            array.remove(array.size() - 1);
        }
    }


    /**
     * 面试题 02.03. 删除中间节点
     * @param node
     */
    public void deleteNode(ListNode node) {
        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;
        next.next = null;
    }

    /**
     * 142. 环形链表 II
     * https://leetcode.cn/problems/linked-list-cycle-ii/?favorite=ex0k24j
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        Set<ListNode> nodeSet = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (nodeSet.contains(cur)) {
                return cur;
            }
            nodeSet.add(cur);
            cur = cur.next;
        }
        return null;
    }
}
